<!doctype html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>验证二叉搜索树 - 算法详解</title>
    <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css">
    <link rel="stylesheet" href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
        }
        .serif-font {
            font-family: 'Noto Serif SC', serif;
        }
        .gradient-text {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
            -webkit-background-clip: text;
            -webkit-text-fill-color: transparent;
            background-clip: text;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
        }
        .card-hover {
            transition: all 0.3s ease;
        }
        .card-hover:hover {
            transform: translateY(-4px);
            box-shadow: 0 20px 40px rgba(0,0,0,0.1);
        }
        .code-block {
            background: #1e1e1e;
            border-radius: 12px;
            overflow: hidden;
        }
        .code-header {
            background: #2d2d2d;
            padding: 12px 20px;
            display: flex;
            align-items: center;
            justify-content: space-between;
        }
        .code-dots {
            display: flex;
            gap: 8px;
        }
        .dot {
            width: 12px;
            height: 12px;
            border-radius: 50%;
        }
        .dot-red { background: #ff5f56; }
        .dot-yellow { background: #ffbd2e; }
        .dot-green { background: #27c93f; }
        pre {
            margin: 0;
            padding: 20px;
            overflow-x: auto;
        }
        code {
            font-family: 'Consolas', 'Monaco', monospace;
            color: #d4d4d4;
            line-height: 1.6;
        }
        .keyword { color: #c586c0; }
        .function { color: #dcdcaa; }
        .string { color: #ce9178; }
        .number { color: #b5cea8; }
        .comment { color: #6a9955; }
        .operator { color: #d4d4d4; }
        .builtin { color: #4ec9b0; }
        @keyframes fadeInUp {
            from {
                opacity: 0;
                transform: translateY(20px);
            }
            to {
                opacity: 1;
                transform: translateY(0);
            }
        }
        .animate-fadeInUp {
            animation: fadeInUp 0.6s ease-out;
        }
        .mermaid {
            display: flex;
            justify-content: center;
            margin: 2rem 0;
        }
        .drop-cap {
            float: left;
            font-size: 4rem;
            line-height: 1;
            font-weight: 700;
            margin-right: 0.5rem;
            margin-top: -0.2rem;
            color: #667eea;
        }
    </style>
</head>
<body class="bg-gray-50">
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 px-6">
        <div class="max-w-4xl mx-auto text-center animate-fadeInUp">
            <h1 class="text-5xl md:text-6xl font-bold mb-6 serif-font">验证二叉搜索树</h1>
            <p class="text-xl md:text-2xl opacity-90 leading-relaxed">
                探索二叉搜索树的验证算法，掌握递归与中序遍历的精妙之处
            </p>
            <div class="mt-8 flex justify-center gap-4">
                <span class="bg-white bg-opacity-20 px-4 py-2 rounded-full text-sm">
                    <i class="fas fa-code mr-2"></i>算法实现
                </span>
                <span class="bg-white bg-opacity-20 px-4 py-2 rounded-full text-sm">
                    <i class="fas fa-clock mr-2"></i>O(n) 时间复杂度
                </span>
                <span class="bg-white bg-opacity-20 px-4 py-2 rounded-full text-sm">
                    <i class="fas fa-layer-group mr-2"></i>递归思想
                </span>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <main class="max-w-6xl mx-auto px-6 py-12">
        <!-- Problem Description -->
        <section class="mb-16 animate-fadeInUp" style="animation-delay: 0.2s;">
            <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                <h2 class="text-3xl font-bold mb-6 flex items-center">
                    <i class="fas fa-puzzle-piece mr-3 text-purple-600"></i>
                    <span class="gradient-text">题目描述</span>
                </h2>
                <div class="prose prose-lg max-w-none">
                    <p class="text-gray-700 leading-relaxed">
                        <span class="drop-cap serif-font">给</span>定一个二叉树，判断其是否是一个有效的二叉搜索树。二叉搜索树（BST）是一种特殊的二叉树结构，它必须满足以下三个条件：
                    </p>
                    <div class="mt-6 grid md:grid-cols-3 gap-4">
                        <div class="bg-purple-50 p-4 rounded-lg border-l-4 border-purple-500">
                            <div class="flex items-center mb-2">
                                <i class="fas fa-chevron-left text-purple-600 mr-2"></i>
                                <h4 class="font-semibold">左子树规则</h4>
                            </div>
                            <p class="text-sm text-gray-600">节点的左子树只包含小于当前节点的数</p>
                        </div>
                        <div class="bg-purple-50 p-4 rounded-lg border-l-4 border-purple-500">
                            <div class="flex items-center mb-2">
                                <i class="fas fa-chevron-right text-purple-600 mr-2"></i>
                                <h4 class="font-semibold">右子树规则</h4>
                            </div>
                            <p class="text-sm text-gray-600">节点的右子树只包含大于当前节点的数</p>
                        </div>
                        <div class="bg-purple-50 p-4 rounded-lg border-l-4 border-purple-500">
                            <div class="flex items-center mb-2">
                                <i class="fas fa-sync-alt text-purple-600 mr-2"></i>
                                <h4 class="font-semibold">递归性质</h4>
                            </div>
                            <p class="text-sm text-gray-600">所有左子树和右子树自身也必须是二叉搜索树</p>
                        </div>
                    </div>
                </div>
            </div>
        </section>

        <!-- Examples -->
        <section class="mb-16 animate-fadeInUp" style="animation-delay: 0.3s;">
            <div class="grid md:grid-cols-2 gap-6">
                <div class="bg-white rounded-2xl shadow-lg p-6 card-hover">
                    <div class="flex items-center mb-4">
                        <i class="fas fa-check-circle text-green-500 text-2xl mr-3"></i>
                        <h3 class="text-xl font-semibold">有效的 BST</h3>
                    </div>
                    <div class="bg-gray-50 p-4 rounded-lg">
                        <p class="font-mono text-center text-lg">[2, 1, 3]</p>
                    </div>
                    <div class="mermaid">
                        graph TD
                            A[2] --> B[1]
                            A --> C[3]
                            style A fill:#10b981,stroke:#059669,color:#fff
                            style B fill:#10b981,stroke:#059669,color:#fff
                            style C fill:#10b981,stroke:#059669,color:#fff
                    </div>
                </div>
                <div class="bg-white rounded-2xl shadow-lg p-6 card-hover">
                    <div class="flex items-center mb-4">
                        <i class="fas fa-times-circle text-red-500 text-2xl mr-3"></i>
                        <h3 class="text-xl font-semibold">无效的 BST</h3>
                    </div>
                    <div class="bg-gray-50 p-4 rounded-lg">
                        <p class="font-mono text-center text-lg">[5, 1, 4, null, null, 3, 6]</p>
                    </div>
                    <div class="mermaid">
                        graph TD
                            A[5] --> B[1]
                            A --> C[4]
                            C --> D[3]
                            C --> E[6]
                            style A fill:#ef4444,stroke:#dc2626,color:#fff
                            style B fill:#10b981,stroke:#059669,color:#fff
                            style C fill:#ef4444,stroke:#dc2626,color:#fff
                            style D fill:#10b981,stroke:#059669,color:#fff
                            style E fill:#ef4444,stroke:#dc2626,color:#fff
                    </div>
                </div>
            </div>
        </section>

        <!-- Core Concepts -->
        <section class="mb-16 animate-fadeInUp" style="animation-delay: 0.4s;">
            <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                <h2 class="text-3xl font-bold mb-6 flex items-center">
                    <i class="fas fa-brain mr-3 text-purple-600"></i>
                    <span class="gradient-text">核心算法</span>
                </h2>
                <div class="flex flex-wrap gap-3 mb-8">
                    <span class="bg-purple-100 text-purple-700 px-4 py-2 rounded-full font-medium">
                        <i class="fas fa-redo mr-2"></i>递归
                    </span>
                    <span class="bg-purple-100 text-purple-700 px-4 py-2 rounded-full font-medium">
                        <i class="fas fa-sort-amount-up mr-2"></i>中序遍历
                    </span>
                    <span class="bg-purple-100 text-purple-700 px-4 py-2 rounded-full font-medium">
                        <i class="fas fa-ruler-combined mr-2"></i>范围验证
                    </span>
                </div>
            </div>
        </section>

        <!-- Solution Approaches -->
        <section class="mb-16 animate-fadeInUp" style="animation-delay: 0.5s;">
            <h2 class="text-3xl font-bold mb-8 text-center">
                <span class="gradient-text">解题思路</span>
            </h2>
            <div class="grid md:grid-cols-2 gap-8">
                <!-- Recursive Approach -->
                <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                    <div class="flex items-center mb-6">
                        <div class="bg-purple-100 p-3 rounded-full mr-4">
                            <i class="fas fa-code-branch text-purple-600 text-2xl"></i>
                        </div>
                        <div>
                            <h3 class="text-2xl font-bold">递归法</h3>
                            <p class="text-gray-600">Range Validation</p>
                        </div>
                    </div>
                    <p class="text-gray-700 mb-4 leading-relaxed">
                        通过递归检查每个节点的取值范围，确保左子树所有节点小于当前节点，右子树所有节点大于当前节点。
                    </p>
                    <div class="bg-gray-50 p-4 rounded-lg">
                        <div class="flex items-center justify-between mb-2">
                            <span class="text-sm font-semibold text-gray-700">
                                <i class="fas fa-clock mr-1"></i>时间复杂度
                            </span>
                            <span class="font-mono text-purple-600">O(n)</span>
                        </div>
                        <div class="flex items-center justify-between">
                            <span class="text-sm font-semibold text-gray-700">
                                <i class="fas fa-memory mr-1"></i>空间复杂度
                            </span>
                            <span class="font-mono text-purple-600">O(h)</span>
                        </div>
                    </div>
                </div>

                <!-- Inorder Traversal -->
                <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                    <div class="flex items-center mb-6">
                        <div class="bg-purple-100 p-3 rounded-full mr-4">
                            <i class="fas fa-stream text-purple-600 text-2xl"></i>
                        </div>
                        <div>
                            <h3 class="text-2xl font-bold">中序遍历法</h3>
                            <p class="text-gray-600">Inorder Traversal</p>
                        </div>
                    </div>
                    <p class="text-gray-700 mb-4 leading-relaxed">
                        BST 的中序遍历结果是递增序列，通过检查遍历结果是否严格递增来验证是否为有效的二叉搜索树。
                    </p>
                    <div class="bg-gray-50